Motion estimation is used for increasing compression efficiency by removing temporal redundancy of input video data in a video coder. General standards for compressing a moving picture are mostly based on block-based coders. Such block-based coders use a block matching algorithm. The block matching algorithm performs block-based motion estimation. According to the block matching algorithm, a block most similar to a certain block in a target image is selected from candidate blocks positioned within a search area of a reference image. Here, the relative local difference between the block to be processed in the target image and the most similar candidate block in the reference image is referred to as a motion vector (MV). Generally, the sum of absolute differences (“SAD”) is calculated for motion estimation.
When a motion estimator is actually designed based on such calculation, the performance and the amount of operation of motion estimation should be considered. For motion estimation, most of the amount of operation is for calculation of the SAD. In other words, subtraction, calculation of an absolute value and a cumulative operation should be performed to calculate each of the SAD for each sub-block in the reference image. In particular, the amount of such calculation is proportional to the size of a block to be processed. According to conventional motion estimation method, it takes a great amount of time and processing power to estimate motion since the SAD operations require a significant amount of time and processing power.
Currently, a hierarchical motion estimation method is used in which the reference image and target image are down sampled before conducting the SAD calculations and comparison of sub-blocks for the reference image and the target image. FIG. 1 illustrates a down sampled reference image and a down sampled target image. According to the hierarchical motion estimation method, a reference image 20 is down sampled to a middle layer 22. The middle layer is down sampled to a lower layer 24. Typically, the lower layer 24 is about 32-pixels by 32-pixels.
Similarly, a 16-pixels by 16-pixels block 28 of the target image 26 is down sampled to a middle layer 30. The middle layer 30 is further down sampled to a target block 32. The target block 32 can be 4-pixels by 4-pixels (“4×4”). Typically, the target block is compared to each sub-block in the lower layer 24 of the reference image. Since the lower layer has 32-pixels by 32-pixels, there are about 841 possible 4×4 sub-blocks within the lower layer 24. Thus, the target block is compared to about 841 sub-blocks of the lower layer 24.
In order to compare the target block to each of the sub-blocks of the lower layer 24, a SAD value can be calculated for each of the comparisons. The corresponding sub-block of the lower layer 24 having the minimum SAD value can be identified as the most similar to the target block 32. Next, the sub-block is up-sampled to an area of the middle layer 22. Additional SAD calculations are performed between the middle layers 22 and 30 to determine the most similar sub-block in the middle layer 22 to the middle layer 30. Once the most similar block is identified, that most similar block is up-sampled to an area of the reference image 20. The block 28 of the target image 26 is further compared to the area of the reference image 20 for identifying the most similar sub-block in the reference image 20.
In total, the number of SAD calculations can range in the hundreds to the thousands depending on the size of the reference image and the target image, thus a motion estimation processor can expend a large amount of time. Typically, the motion estimation processor will calculate one SAD calculation at a time, by reading the pixel data for the sub-block of the lower layer 24 and the target block 32, calculating the SAD calculation, storing that SAD value for that comparison, and calculating a next SAD calculation for the next sub-block of the lower layer 24 to be compared. Once all the SAD values are calculated, the minimum is chosen as the most similar sub-block of the lower layer 24 to the target block. This process is very time consuming. Therefore, there exists a need to further improve such method to enhance performance to quickly identify a similar sub-block of the lower layer to a target block.